<html>
<head><meta charset="utf-8"><title>algo::diff · t-compiler/rust-analyzer · Zulip Chat Archive</title></head>
<h2>Stream: <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/index.html">t-compiler/rust-analyzer</a></h2>
<h3>Topic: <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/algo.3A.3Adiff.html">algo::diff</a></h3>

<hr>

<base href="https://rust-lang.zulipchat.com">

<head><link href="https://rust-lang.github.io/zulip_archive/style.css" rel="stylesheet"></head>

<a name="214446649"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/algo%3A%3Adiff/near/214446649" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Lukas Wirth <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/algo.3A.3Adiff.html#214446649">(Oct 24 2020 at 20:04)</a>:</h4>
<p>I just realized a big mistake I made when rewriting the algo::diff function. The generated diff is now all over the place when something has been inserted or deleted due to those changes offsetting the nodes. As in an insert in a node causes all nodes beyond that point(including the inserted node) to be marked as replacements so diffing is anything but minimal now. I just realized that while trying to integrate my recent changes into the auto import cursor fix branch because the cursor now jumps even further instead of not jumping at all.</p>



<a name="214446753"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/algo%3A%3Adiff/near/214446753" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Lukas Wirth <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/algo.3A.3Adiff.html#214446753">(Oct 24 2020 at 20:06)</a>:</h4>
<p>One solution I could think of is to check if the current node we are looking at is at the same position in the other tree or a next_sibling of the node at that position which would allow to do proper judgement about whether this was an insertion or not but this feels like causing runtime complexity to skyrocket I think?</p>



<a name="214558914"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/algo%3A%3Adiff/near/214558914" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/algo.3A.3Adiff.html#214558914">(Oct 26 2020 at 10:53)</a>:</h4>
<p>I wouldn't worry too much about runtime complexity</p>



<a name="214558921"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/algo%3A%3Adiff/near/214558921" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/algo.3A.3Adiff.html#214558921">(Oct 26 2020 at 10:53)</a>:</h4>
<p>Stuff is mostly small, etc.</p>



<a name="214559065"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/algo%3A%3Adiff/near/214559065" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> matklad <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/algo.3A.3Adiff.html#214559065">(Oct 26 2020 at 10:55)</a>:</h4>
<p>I would worry a lot about implementation complexity -- diff-ing is not the prettiest code there is, and it's already a lot of it. It's not inconceivable that there's some order-of-magnitude better way to handle this :-) The current diffing was explicitly written as the simplest thing I can come up with in n minutes, I wish we used something more principled.</p>



<a name="214577408"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/algo%3A%3Adiff/near/214577408" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Lukas Wirth <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/algo.3A.3Adiff.html#214577408">(Oct 26 2020 at 14:07)</a>:</h4>
<p>I see, I did look around a bit for proper node/ast based diff algorithms but I only found a few things that were too complex for me atm <span aria-label="sweat smile" class="emoji emoji-1f605" role="img" title="sweat smile">:sweat_smile:</span></p>



<a name="214577493"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/185405-t-compiler/rust-analyzer/topic/algo%3A%3Adiff/near/214577493" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Lukas Wirth <a href="https://rust-lang.github.io/zulip_archive/stream/185405-t-compiler/rust-analyzer/topic/algo.3A.3Adiff.html#214577493">(Oct 26 2020 at 14:07)</a>:</h4>
<p>I would make another PR that does the look-ahead in algo::diff to properly find insertions if that is alright then because that is the only blocker(after merging the SyntaxRewriter changes) left for the auto-import cursor jumping</p>



<hr><p>Last updated: Aug 07 2021 at 22:04 UTC</p>
</html>